public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().lastStoneWeightII(new int[]{2,7,4,1,8,1}));
        System.out.println(new Solution().lastStoneWeightII(new int[]{31,26,33,21,40}));
    }
}


class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int each : stones) {
            sum += each;
        }

        int half = sum / 2;

        boolean[] dp = new boolean[half + 1];
        dp[0] = true;
        for (int each : stones) {
            for (int i = half; i >= each; i--) {
                dp[i] = dp[i] || dp[i - each];
            }
        }

        int best = 0;
        for (int i = half; i >= 0; i--) {
            if (dp[i]) {
                best = i;
                break;
            }
        }
        return sum - best - best;
    }
}
